#include <bits/stdc++.h>
// 2025/02/06
// tag:
// Author: Zhang Muen
using namespace std;

using int64 = int64_t;

int n, m, zv[61], zw[61], dp[32001];
vector<int> value[61], imp[61], v[61], w[61];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        zv[i] = -1, zw[i] = -1;
        int x, y, z;
        cin >> x >> y >> z;
        if (z == 0)
            zv[i] = x, zw[i] = y * x;
        else
            value[z].push_back(x), imp[z].push_back(y * x);
    }
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        if (zv[i] == -1)
            continue;
        cnt++;
        v[cnt].push_back(zv[i]), w[cnt].push_back(zw[i]);
        if (value[i].size() >= 1)
            v[cnt].push_back(zv[i] + value[i][0]), w[cnt].push_back(zw[i] + imp[i][0]);
        if (value[i].size() == 2)
            v[cnt].push_back(zv[i] + value[i][0] + value[i][1]), w[cnt].push_back(zw[i] + imp[i][0] + imp[i][1]), v[cnt].push_back(zv[i] + value[i][1]), w[cnt].push_back(zw[i] + imp[i][1]);
    }
    for (int k = 1; k <= cnt; k++)
        for (int i = n; i >= 0; i--)
            for (int j = 0; j < v[k].size(); j++)
                if (i >= v[k][j])
                    dp[i] = max(dp[i], dp[i - v[k][j]] + w[k][j]);
    cout << dp[n] << endl;
    return 0;
}